package main.java.indi.zyj.c150.array;

import java.util.Comparator;
import java.util.PriorityQueue;

public class _02_smallestK {

    public int[] smallestK(int[] arr, int k) {

        int[] vec = new int[k];
        if (k == 0){
            return vec;
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        // 将前k个数字放进去，维护k个大根堆
        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            // 如果小于峰顶就把它放进去，把峰顶扔出去
            if (arr[i] < queue.peek()){
                queue.poll();
                queue.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            vec[i] = queue.poll();
        }

        return vec;
    }
}
